package cn.djb.day15;

/**
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {

    int target;

    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {

        this.target = target;

        ArrayList<Integer> list = new ArrayList<>();
        dfs(root, 0, list);

        return res;


    }


    private void dfs(TreeNode node, int sum, List<Integer> routes) {
        if (node == null) {
            return;
        }

        TreeNode left = node.left;
        TreeNode right = node.right;
        routes.add(node.val);
        sum = sum + node.val;
        if (left == null && right == null && target == sum) {
            res.add(new ArrayList<Integer>(routes));
            return;
        }
        if (left != null) {
            //这里为了不影响到 right计算 所以拷贝对象
            int leftSum = sum;
            dfs(left, leftSum, new ArrayList<Integer>(routes));
        }
        if (right != null) {
            dfs(right, sum, routes);
        }

    }


    /**
     * 广度优先遍历
     * 不合适
     *
     * @param root
     * @param target
     * @return
     */
    @Deprecated
    public List<List<Integer>> bfs(TreeNode root, int target) {

        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        //存储路径和
        Queue<Integer> queueNum = new LinkedList<>();
        queue.add(root);
        queueNum.add(root.val);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            Integer pathSum = queueNum.poll();
            TreeNode left = poll.left;
            TreeNode right = poll.right;
            if (left == null && right == null){

            }


        }

        return res;


    }

}